package com.cuz.daileetcode.bat100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 数组arr之间添加加or减号使结果为target的方法数 {

    public static void main(String[] args) {
        int[] ints = {1, 0};
//        int ways1 = solution1(ints, 6);
//        int ways2 = solution2(ints, 6);
//        int ways3 = solution3(ints, 6);
//        int ways4 = solution4(ints, 3);
        int ways5 = solution5(ints, 1);
//        System.out.println(ways1);
//        System.out.println(ways2);
//        System.out.println(ways3);
//        System.out.println(ways4);
        System.out.println(ways5);
    }

    private static int solution2(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //数组每一个元素取绝对值 并求和
        int sum = absThenSum(arr);
        int targetAbs = Math.abs(target);
        //和 小于target绝对值===> （[1,2,3] target=10 or -10）不可以能做到
        if (sum < targetAbs) {
            return 0;
        }
        // sum 和 targetAbs 奇偶性不同 返回0
        //【1 2 3】 target=5 必不可能
        if (isOdd(sum) != isOdd(targetAbs)) {
            return 0;
        }
        //后缀和 数组 suffixSumArray[x]表示【x+1....arr.length-1 和是多少
        int[] suffixSumArray = suffixSum(arr, sum);
        return process2(arr, 0, 0, target, suffixSumArray);
    }

    private static int process2(int[] arr, int curIndex, int curRes,
                                int target,
                                int[] suffixSumArray) {
        if (curIndex == arr.length && curRes == target) {
            return 1;
        }
        if (curIndex == arr.length) {
            return 0;
        }
        //全加上 全减去 都无法凑出target
        //【1，2，3】curRes=-1 curIndex=1 target= 6 （-1+2+3）<6
        //1，2，3】curRes=1 curIndex=1 target=-6 (1-2-3)>-6
        if (curIndex > 0 && ((curRes + suffixSumArray[curIndex - 1]) < Math.abs(target)
                || (curRes - suffixSumArray[curIndex - 1]) > target)) {
            return 0;
        }
        int ans = process2(arr, curIndex + 1, curRes + arr[curIndex], target, suffixSumArray);
        ans += process2(arr, curIndex + 1, curRes - arr[curIndex], target, suffixSumArray);
        return ans;
    }

    private static int solution1(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //数组每一个元素取绝对值 并求和
        int sum = absThenSum(arr);
        int targetAbs = Math.abs(target);
        //和 小于target绝对值===> （[1,2,3] target=10 or -10）不可以能做到
        if (sum < targetAbs) {
            return 0;
        }
        // sum 和 targetAbs 奇偶性不同 返回0
        //【1 2 3】 target=5 必不可能
        if (isOdd(sum) != isOdd(targetAbs)) {
            return 0;
        }
        //arrArray[0] 记录答案
        int[] ansArray = {0};
        //后缀和 数组 suffixSumArray[x]表示【x+1....arr.length-1 和是多少
        int[] suffixSumArray = suffixSum(arr, sum);
        process1(arr, 0, 0, target, ansArray, suffixSumArray);
        return ansArray[0];
    }

    /***
     * 从 curIndex 开始向arr.length-1选择让curRes+ or -
     * 如果凑出 target 那么ansArray[0]++
     * 如果后续的数 全- or 全+ 都凑不出target 那么剪枝
     * @param arr 可以选择的数
     * @param curIndex 当前位置
     * @param curRes 之前选择的数的结果
     * @param target 目标数
     * @param ansArray 结果
     * @param suffixSumArray 后缀和
     */
    private static void process1(int[] arr, int curIndex, int curRes,
                                 int target, int[] ansArray,
                                 int[] suffixSumArray) {
        if (curIndex == arr.length && curRes == target) {
            ansArray[0]++;
            return;
        }
        if (curIndex == arr.length) {
            return;
        }
        //全加上 全减去 都无法凑出target
        //【1，2，3】curRes=-1 curIndex=1 target= 6 （-1+2+3）<6
        //1，2，3】curRes=1 curIndex=1 target=-6 (1-2-3)>-6
        if (curIndex > 0 && ((curRes + suffixSumArray[curIndex - 1]) < Math.abs(target)
                || (curRes - suffixSumArray[curIndex - 1]) > target)) {
            return;
        }
        process1(arr, curIndex + 1, curRes + arr[curIndex], target, ansArray, suffixSumArray);
        process1(arr, curIndex + 1, curRes - arr[curIndex], target, ansArray, suffixSumArray);
    }

    /***
     * 数组后缀和
     * @param arr 求arr的后缀和
     * @param sum 数组总和
     * @return 后缀和数组
     * 【1 ，2，3】 ==> [5,3,0]
     */
    private static int[] suffixSum(int[] arr, int sum) {
        int[] res = new int[arr.length];
        for (int index = 0; index < arr.length; index++) {
            sum -= arr[index];
            res[index] = sum;
        }
        return res;
    }

    /**
     * 数组元素处理为非负数数 并且返回总和
     *
     * @param arr 数组
     * @return 总和
     */
    private static int absThenSum(int[] arr) {
        int sum = 0;
        for (int index = 0; index < arr.length; index++) {
            arr[index] = Math.abs(arr[index]);
            sum += arr[index];
        }
        return sum;
    }

    /**
     * num 是否为奇数
     */
    private static boolean isOdd(int num) {
        //3==>011 & 1 ===>001=>1
        //4=>100 & 1==>000=>0
        return (num & 1) == 1;
    }


    private static int solution3(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //数组每一个元素取绝对值 并求和
        int sum = absThenSum(arr);
        int targetAbs = Math.abs(target);
        //和 小于target绝对值===> （[1,2,3] target=10 or -10）不可以能做到
        if (sum < targetAbs) {
            return 0;
        }
        // sum 和 targetAbs 奇偶性不同 返回0
        //【1 2 3】 target=5 必不可能
        if (isOdd(sum) != isOdd(targetAbs)) {
            return 0;
        }
        //后缀和 数组 suffixSumArray[x]表示【x+1....arr.length-1 和是多少
        int[] suffixSumArray = suffixSum(arr, sum);
        HashMap<Integer, Map<Integer, Integer>> memory = new HashMap<>();
        return process3(arr, 0, 0, target, suffixSumArray, memory);
    }

    private static int process3(int[] arr, int curIndex, int curRes,
                                int target,
                                int[] suffixSumArray, HashMap<Integer, Map<Integer, Integer>> memory) {
        Map<Integer, Integer> curIndexMap = memory.getOrDefault(curIndex,
                new HashMap<>());
        Integer valueInMemory = curIndexMap.get(curRes);
        if (valueInMemory != null) {
            return valueInMemory;
        }
        int ans;
        if (curIndex == arr.length && curRes == target) {
            ans = 1;
        } else if (curIndex == arr.length) {
            ans = 0;
        }
        //全加上 全减去 都无法凑出target
        //【1，2，3】curRes=-1 curIndex=1 target= 6 （-1+2+3）<6
        //1，2，3】curRes=1 curIndex=1 target=-6 (1-2-3)>-6
        else if (curIndex > 0 && ((curRes + suffixSumArray[curIndex - 1]) < Math.abs(target)
                || (curRes - suffixSumArray[curIndex - 1]) > target)) {
            ans = 0;
        } else {
            ans = process3(arr, curIndex + 1, curRes + arr[curIndex], target, suffixSumArray, memory);
            ans += process3(arr, curIndex + 1, curRes - arr[curIndex], target, suffixSumArray, memory);
        }
        curIndexMap.put(curRes, ans);
        memory.put(curIndex, curIndexMap);
        return ans;
    }


    private static int solution4(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //数组每一个元素取绝对值 并求和
        int sum = absThenSum(arr);
        int targetAbs = Math.abs(target);
        //和 小于target绝对值===> （[1,2,3] target=10 or -10）不可以能做到
        if (sum < targetAbs) {
            return 0;
        }
        // sum 和 targetAbs 奇偶性不同 返回0
        //【1 2 3】 target=5 必不可能
        if (isOdd(sum) != isOdd(targetAbs)) {
            return 0;
        }
        //后缀和 数组 suffixSumArray[x]表示【x+1....arr.length-1 和是多少
        int[] suffixSumArray = suffixSum(arr, sum);
        //0~sum 列表示 -sum ~ 0
        int[][] memory = new int[arr.length + 1][2 * (sum + 1)];
        for (int[] ints : memory) {
            Arrays.fill(ints, -sum - 1);
        }
        return process4(arr, 0, 0, target, suffixSumArray, sum, memory);
    }

    private static int process4(int[] arr, int curIndex, int curRes,
                                int target,
                                int[] suffixSumArray, int sum, int[][] memory) {
        int ans = memory[curIndex][curRes + sum];
        if (ans != -sum - 1) {
            return ans;
        }
        if (curIndex == arr.length && curRes == target) {
            ans = 1;
        } else if (curIndex == arr.length) {
            ans = 0;
        }
        //全加上 全减去 都无法凑出target
        //【1，2，3】curRes=-1 curIndex=1 target= 6 （-1+2+3）<6
        //1，2，3】curRes=1 curIndex=1 target=-6 (1-2-3)>-6
        else if (curIndex > 0 && ((curRes + suffixSumArray[curIndex - 1]) < Math.abs(target)
                || (curRes - suffixSumArray[curIndex - 1]) > target)) {
            ans = 0;
        } else {
            ans = process4(arr, curIndex + 1, curRes + arr[curIndex], target, suffixSumArray, sum, memory);
            ans += process4(arr, curIndex + 1, curRes - arr[curIndex], target, suffixSumArray, sum, memory);
        }
        memory[curIndex][curRes + sum] = ans;
        return ans;
    }


    private static int solution5(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //数组每一个元素取绝对值 并求和
        int sum = absThenSum(arr);
        int targetAbs = Math.abs(target);
        //和 小于target绝对值===> （[1,2,3] target=10 or -10）不可以能做到
        if (sum < targetAbs) {
            return 0;
        }
        // sum 和 targetAbs 奇偶性不同 返回0
        //【1 2 3】 target=5 必不可能
        if (isOdd(sum) != isOdd(targetAbs)) {
            return 0;
        }
        //后缀和 数组 suffixSumArray[x]表示【x+1....arr.length-1 和是多少
        int[] suffixSumArray = suffixSum(arr, sum);
        //P-Q=Target P+Q=sum
        //2*P=Target+sum

        //P=(Target+Sum)/2===>选择任意个数相加构成(Target+Sum)/2
        int[][] memory = new int[arr.length + 1][((target + sum) / 2) + 1];
        for (int[] ints : memory) {
            Arrays.fill(ints, -1);
        }
        return process5(arr, 1, arr[0], (target + sum) / 2, memory)
        +process5(arr, 1, 0, (target + sum) / 2, memory);

    }

    private static int process5(int[] arr, int curIndex, int curRes, int target, int[][] memory) {
        int ans = memory[curIndex][curRes];
        if (ans != -1) {
            return ans;
        }
        if (curRes == target) {
            ans = 1;
        } else if (curIndex == arr.length) {
            ans = 0;
        } else {
            ans = process5(arr, curIndex + 1, curRes + arr[curIndex], target, memory);
            ans += process5(arr, curIndex + 1, curRes, target, memory);
        }
        memory[curIndex][curRes] = ans;
        return ans;
    }
}
